#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

// 打印访问顺序和平均移动道数
void print_result(const vector<int>& order, int start, const string& algo) {
    int total_move = 0, cur = start;
    cout << "\n[" << algo << "] 访问顺序: ";
    for (int i = 0; i < order.size(); ++i) {
        cout << order[i];
        if (i != order.size() - 1) cout << " -> ";
        total_move += abs(order[i] - cur);
        cur = order[i];
    }
    cout << "\n总移动道数: " << total_move
         << "，平均移动道数: " << fixed << setprecision(2) << (double)total_move / order.size() << endl;
}

// 先来先服务 FCFS
void schedule_FCFS(const vector<int>& requests, int start) {
    print_result(requests, start, "先来先服务 FCFS");
}

// 最短寻道优先 SSTF
void schedule_SSTF(vector<int> requests, int start) {
    vector<int> order;
    int cur = start;
    vector<bool> visited(requests.size(), false);
    for (int i = 0; i < requests.size(); ++i) {
        int idx = -1, min_dist = 1e9;
        for (int j = 0; j < requests.size(); ++j) {
            if (!visited[j]) {
                int dist = abs(requests[j] - cur);
                if (dist < min_dist) {
                    min_dist = dist;
                    idx = j;
                }
            }
        }
        order.push_back(requests[idx]);
        visited[idx] = true;
        cur = requests[idx];
    }
    print_result(order, start, "最短寻道优先 SSTF");
}

// 电梯调度 SCAN（向磁道号增加方向移动）
void schedule_SCAN(vector<int> requests, int start) {
    vector<int> order;
    vector<int> up, down;
    for (int r : requests) {
        if (r >= start) up.push_back(r);
        else down.push_back(r);
    }
    sort(up.begin(), up.end());
    sort(down.begin(), down.end());
    // 先向上，再向下
    for (int r : up) order.push_back(r);
    for (int r : down) order.push_back(r);
    print_result(order, start, "电梯调度 SCAN");
}

int main() {
    vector<int> requests = {30,50,100,180,20,90,150,70,80,10,160,120,40,110};
    int start = 90;

    schedule_FCFS(requests, start);
    schedule_SSTF(requests, start);
    schedule_SCAN(requests, start);

    return 0;
}